// BiTree.cpp

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

enum Status
{
    OK = 0,
    ERROR = 1,
};

// 前序遍历 DLR
Status PreOrderTraverse(BiTree T, Status(*Visit)(int n))
{
    // 最简单的visit函数是：
    /*
        Status PrintElement(int n)
        {
            printf(n);
            return OK;
        }

    调用: PreOrderTraverse(T, PrintElement);
    */

   if(T)
   {
       if(Visit(T->data))
       {
           if(PreOrderTraverse(T->lchild, Visit))
           {
               if(PreOrderTraverse(T->rchild, Visit))
               {
                   return OK;
               }
           }
       }

       return ERROR;
   }

   return ERROR;
}

// 中序遍历 LDR
Status InOrderTraverse(BiTree T, Status(*Visit)(int n))
{
   if(T)
   {
       if(PreOrderTraverse(T->lchild, Visit))
       {
           if(Visit(T->data))
           {
               if(PreOrderTraverse(T->rchild, Visit))
               {
                   return OK;
               }
           }
       }

       return ERROR;
   }

   return ERROR;
}

// 后序遍历 LRD
Status PostOrderTraverse(BiTree T, Status(*Visit)(int n))
{
   if(T)
   {
       if(PreOrderTraverse(T->lchild, Visit))
       {
           if(PreOrderTraverse(T->rchild, Visit))
           {
               if(Visit(T->data))
               {
                   return OK;
               }
           }
       }

       return ERROR;
   }

   return ERROR;
}

// 二叉树的二叉线索存储表示
typedef int TElemType;
typedef enum PointerTag {Link, Thread};     // Link == 0，指针；Thread == 1，线索；
typedef struct BiThrNode
{
    TElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(TElemType e))
{
    BiThrNode *p = T->lchild;

    while (p != T)
    {
        while(p->LTag == Link)
        {
            p = p->lchild;
        }
        if(!Visit(p->data))
        {
            return ERROR;
        }
        while(p->RTag == Thread && p->rchild != T)
        {
            p = p->rchild;
            Visit(p->data);
        }

        p = p->rchild;
    }
    
    return OK;
}

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{
    // 中序遍历二叉树T，并将其中序线索华，Thrt指向头结点。
    if(!(Thrt = new BiThrNode))
    {
        return ERROR;
    }

    Thrt->LTag = Link;
    Thrt->RTag = Thread;

    Thrt->rchild = Thrt;

    if(!T)
    {
        Thrt->lchild = Thrt;
    }
    else
    {
        Thrt->lchild = T;
        BiThrNode *pre = Thrt;
        InThreading(T);
        pre->rchild = Thrt;
        pre->RTag = Thread;
        Thrt->rchild = pre;
    }

    return OK;
}

void InThreading(BiThrTree p)
{
    if(p)
    {
        BiThrNode *pre = new BiThrNode;
        InThreading(p->lchild);
        if(!p->lchild)
        {
            p->LTag = Thread;
            p->lchild = pre;
        }
        if(!p->rchild)
        {
            pre->RTag = Thread;
            pre->rchild = p;
        }
        
        pre = p;

        InThreading(p->rchild);
    }
}

